package com.wufeng.leetcode;

/**
 * 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 * 说明：你不能倾斜容器，且 n 的值至少为 2。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/container-with-most-water
 */
public class MaxWater {

    /**
     * 暴力遍历法
     * 双重循环遍历，找到所有可能的情况并计算出最大面积，最后得出最大值。
     *
     * @param heights
     * @return
     */
    public int maxArea1(int[] heights) {
        int maxArea = 0;
        for (int front = 0; front < heights.length - 1; front++) {
            for (int behind = front + 1; behind < heights.length; behind++) {
                int calcArea = Math.min(heights[front], heights[behind]) * (behind - front);
                maxArea = Math.max(maxArea, calcArea);
            }
        }
        return maxArea;

    }

    /**
     * 算法求解：数组双指针遍历
     * 从数组的两头向中间遍历，需要求大最大面积的值，面积 = 长 * 宽 。长变小，如果像取到大的值，就需要移动宽小的那个
     * 即 比较前后两个高度，高度低的那个去移动遍历，这样才可能取到可能大的值，移动大的值可能面积会变小的。
     *
     * @param height
     * @return
     */
    public int maxArea2(int[] height) {
        int maxArea = 0;
        int front = 0;
        int behind = height.length - 1;
        while (front < behind) {
            int calcArea = (behind - front) * Math.min(height[front], height[behind]);
            maxArea = Math.max(maxArea, calcArea);
            if (height[front] < height[behind]) {
                front++;
            } else {
                behind--;
            }
        }
        return maxArea;
    }

}
